Final Lab (Hooray!)

April 26, 2013

Prelab (complete before lab)

Ensure you can still access the CS servers.

Part 1

In this lab, we will be writing a complete, if simple, C program. Specifically, we will make a version of a text-based adventure game. This program will show you how to allocate memory dynamically, review structures, review input/output, and give you a feel for a somewhat larger C program.

First, let us write our program header and a loop that takes user input.  Create the following main function:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct place {
    char *description;
    struct place *dir[4];
} place;
    
int main()
{
    int direction;
    place *here;
    
    here = (place *) malloc(sizeof(place));
    here->description = "Surrounding you in all directions is a foggy mist\n";
    direction = 0;
    while (direction < 5) {
	printf("%s", here->description);
        printf("1) Go north\n");
        printf("2) Go south\n");
        printf("3) Go east\n");
        printf("4) Go west\n");
        printf("5) Exit\n");
	printf("Command: ");
	scanf("%d", &direction);
    }
}

Within the main function,  there is a loop that either moves or terminates when a user enters the value of an integer.  The options are "1) Go north", "2) Go south", "3) Go east", "4) Go west", and "5) Exit".  The function  scanf() is used to get the user's numeric response.

As we do not have saved game data, our "game" is going to be constructed by the player as they go. In this game, the player can move north, south, east, or west, and whenever they move, they get a description of the area into which they have moved.

Together the places in the game and how they are connected together form a graph.   The graph grows dynamically based on where the player walks, so new vertices must be allocated.  To store a vertex, we use the C struct named place and its associated typedef. This struct has a string for the description of the place and four pointers to the neighboring places. The string for the description is just a pointer to a string, not an allocated string (i.e. char* ), and pointers to the four adjacent vertices/places are given in the dir. You can assume the 0, 1, 2, and 3 indices refer to other places north, south, east and west of the current place, respectively.

Compile and test the given code to make sure it only exits when you enter '5'.

Part 2

Now we have a data type to build our graph and a loop for user input.  Next, let us make a factory function for generating instances of place. A factory function is a function that allocates a properly initialized struct of a specific type for you and returns its pointer.  These are especially useful in C as C structs do not have constructors like Java and C++ classes do.

Write a function that takes a pointer to a string as an argument and returns a pointer to a place. The first thing this factory function needs to do is to allocate memory for a new place object. To do this, we use malloc(). An example of malloc() is shown in the original code fragment. Malloc() allocates N bytes of memory, where N is the argument given to malloc. To allocate enough bytes of memory for a place struct, use the built-in sizeof() function, which returns the number of bytes a given type uses.

place *new_place = malloc(sizeof(place));

The factory function should also initialize elements of the struct.  In our case, the four dir[] pointers, (north, south, east, and west) should all be initialized to 0. And the description element should be initialized to the string argument that is passed in to the function.

Now we are ready to start. First, add the code for your place_factory(), then modify the main program, to make use of your new factory function to generate the node here (see the code before the while loop), and change the description to "You are standing in an open field west of a white house.\n".

Compile your new version, and verify that it works like before, but with the new place description

Checkoff 1.  Provide the code for your place factory function.

Part 3

Now we just need to let the user populate the graph as they walk around.  Add a pointer to a place struct that points to the origin. We will refer to this pointer as the 'current place'.

Within the user input loop, create an if statement that is triggered if the user selects to go north, i.e. enters a '1'. Within this loop we want to

1. Check if the dir[0] entry of the current place is 0.
2. If it is,
3.      Prompt the user to enter a description,
4.      Allocate a new place, using your place factory function
5.      Set the current place's north pointer (dir[0]) to point to the new place,
6.      Set the new place's south pointer (dir[1]) to point to the current place,
7.      Set the current place to be the new place.
8. else,
9.      Set the current place to be the place to the north.

One difficulty here is reading a full description, which will likely be multiple words.  The easiest way to read such a description is to use the getline() function. This function takes three arguments: a pointer to a string, a pointer to an integer, and "stdin", which tells the function to read from the console.  The string argument must be allocated beforehand, and the integer second argument should be the number of characters in the string.  e.g.

int size = 50;
char* desc = (char*)malloc(size + 1);
getline(&desc, &size,  stdin);

Checkoff 2.  Why is 1 added to size when allocating the description?

We can now use something like the above to get a description from the user.  One caveat, though, is that mixing scanf and getline is tricky.  scanf only reads one string, so it will leave the implied '\n' character on the input buffer.  If we call a getline directly after a scanf, we will only get that last '\n' character.  To use this, then, we must make a throwaway call after our scanf().  We can do this cleanly with a function such as 

void clear_input() {
    int max = 10;
    char *throwout = (char*) malloc(max + 1);
    getline(&throwout, &max, stdin);
}
...

scanf("%i", &input);
clear_input();

...
getline(&whatever, &size, stdin);

Now you should be able to implement the pseudocode given above. Remember that pointers to structure elements use the -> operator instead of the . operator.

Checkoff 3. Give your C code for the above pseudocode.

Part 4

Test your code above by walking north and creating new places.  You should also be able to walk south and visit places you already made.  

Now we just need to expand our program to handle south, east, and west.  Expand the if statement to handle these cases.  You should be able to copy your 'north' code directly and then use find/replace to make all the needed changes.

You should now be able to walk in any direction, creating places as you go.

Checkoff 4. What's the best place description you wrote?

Part 5

When you allocate memory dynamically, you need to free it when you are done using it.  To do this, we use the free() command,

struct place* my_place = place_factory("This is a cool place");
...
free(my_place);

In our case, this is not strictly needed as the memory is freed when the program exits.

Checkoff 5. Describe how you would free all the allocated memory in the graph if you needed to.  You do not need to give C code, merely describe your approach. Are there any pitfalls?